1. Field of the Invention
This invention relates to apparatus and methods for implementing a real-time hash map.
2. Background of the Invention
In computer science, a hash table or hash map (collectively referred to hereinafter as a “hash map”) is a data structure that is used extensively in different types of software. A hash map uses a hash function to map identifying values, known as keys, to their associated values. The hash function transforms the key into an index (i.e., a hash code or derivative thereof) associated with an array element (a slot or bucket) where the associated value is located or potentially located.
When a hash map is full or has reached a certain load factor (e.g. 75 percent full), various hash map implementations attempt to resize the hash map. For example, in the Java HashMap class, a hash map is automatically resized when the hash map reaches a specified load factor. To resize the hash map, the Java HashMap class allocates a new larger table. Entries from the previous table are then copied to the new table either all at once or gradually over a period of time. Once all entries are copied from the previous table to the new table, the previous table is de-allocated and returned to the free storage pool.
Nevertheless, conventional hash maps such as those implemented by the Java HashMap class suffer from the following shortcomings. First, conventional hash maps are often pre-allocated larger than they need to be to avoid the resize operation, which can negatively affect real-time operation and provide inconsistent performance. Second, Java users working with primitive data types such as strings have no control over the hash codes that are generated for the strings. This typically increases the number of hash collisions that occur in an application. There is little that can be done to address this problem other than to make the hash map larger than it needs to be. Third, in conventional hash maps, hot and cold data is stored together in the same hash map table. As a result, when looking up data in the hash map, collisions may occur between needed data and rarely referenced data, thereby decreasing performance.
In view of the foregoing, what is needed is a hash map that overcomes many of the shortcomings of conventional hash maps. In particular, a hash map is needed that provides consistent real-time performance. Further needed is a hash map that can be resized in an efficient manner with minimal impact on performance. Such a hash map would ideally allow the initial size of the hash map to be made smaller, thus more efficiently utilizing space.